package Permutations

/*
全排列：和昨天相似，使用回溯算法
1：由于数值不能重复，所以需要记录路径
2：递归之后，释放可选数值，还要将路径选的数值删除掉，这样才可以重复使用
 */


var destination [][]int
func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return [][]int{}
	}
	destination = [][]int{}
	findallnumbersqueen(nums , []int{} , make([]bool , 6))
	return destination
}

func findallnumbersqueen(nums []int , pathnumber []int , used []bool) {
	if len(nums) == len(pathnumber) {
		tmp := make([]int , len(nums))
		copy(tmp , pathnumber)
		destination = append(destination , tmp)
		return
	}
	for i := 0 ; i < len(nums) ; i ++ {
		if ! used[i] {
			used[i] = true
			pathnumber = append(pathnumber , nums[i])
			findallnumbersqueen(nums , pathnumber , used)
			pathnumber = pathnumber[:len(pathnumber) - 1]
			used[i] = false
		}
	}
}